Instrumentation is a technique that can enable engineers to comprehend, monitor, and assess the operation of software. Typically, a program is instrumented by inserting probes at various points in the program, where the probes report a variety of information, typically by printing to a file. This information, referred to as instrumented data, might include indications of whether certain portions of a program have been reached (referred to as coverage), the number of times that various portions of the program have been executed (referred to as execution counts), how much time is spent in various portions of the program, and so forth. Instrumentation thus facilitates the identification of coverage efficiency, bottlenecks, bugs, and other deficiencies in a program and, consequently, can aid in the process of improving the quality, security, efficiency, and performance of programs.
The introduction of probes into a program, however, adds overhead that can slow down the execution of the program, and thus there is a tradeoff when inserting probes into a program. Ideally, the probes should cover all of the various execution paths of the program, and should be sufficient in number so that the reported information is fine-grained enough to be useful. However, if there are too many probes, then program runtime performance might suffer appreciably, which is unacceptable in applications such as real-time embedded systems and Voice over Internet Protocol (VoIP). Similarly, printing instrumented data to a file can slow execution to a degree that is unacceptable in real-time systems.
Some methods for determining probe insertion points in a program are based on a control-flow graph that is derived from the program. FIG. 1 depicts illustrative program 100, and FIG. 2 depicts control-flow graph 200 corresponding to program 100, both in accordance with the prior art. As shown in FIG. 2, control-flow graph 200 comprises nodes 201-1 through node 201-13, connected by arcs as shown. For convenience, each node of control-flow graph 200 has been assigned a label that indicates the portion of program 100 (known as a basic block) to which it corresponds.